It is widely recognized that future wireless systems will be cognitive and be able to use radio spectrum opportunistically. There are a number of standardization bodies (e.g. Institute of Electrical and Electronics Engineers (IEEE) 802.22) and regulatory bodies (e.g. Federal Communications Commission (FCC06, FCCM06)) defining technical requirements for such systems. A central problem in such systems is to obtain spectrum occupancy in a wideband spectral region of interest. For example, the FCC is considering a spectrum in a region from 54 MHz to 862 MHz for such cognitive networks. Similar interest has arisen in a spectrum in a region from 2 GHz to 5 GHz.
In the field of spectrum estimation, a technique called “compressive sensing” has been developed recently. To estimate the spectrum an autocorrelation sequence of length N,r=[r(1) . . . r(N)]T  (1)is required, where each entryr(n)=E{x(t)x*(t−τn)}, n=1, . . . , N  (2)corresponds to an autocorrelation of a received signal x(t) at a specific time delay τn=(n−1)Δt. The sampling time Δt corresponds to the inverse of a total bandwidth of the frequency band to be sensed. The length N of the autocorrelation sequence corresponds to the frequency resolution, i.e., the larger the N, the better the frequency resolution of the estimated spectrum. The spectrum can be estimated as a Fourier transform of the autocorrelation sequence r in equation (1). In matrix form, the estimated spectrum vector is:rf=Fr  (3)where F denotes a Discrete Fourier Transform (DFT) matrix of size N×N.
An exemplary compressive sensing (CS) framework is described in D. Donoho, “Compressed sensing”, IEEE Transactions on Information Theory, pp 1289-1306, April 2006. Assuming that xεRN is a signal, and Ψ=[ψ1 . . . ψN] is a basis of vectors spanning RN, it can be said that x is K-sparse in Ψ, if x can be well approximated by a linear combination of K<<N vectors from Ψ. In matrix form that is:x=Ψθ  (4)where θ is a sparse vector containing K non-zero entries. The CS theory states that it is possible to use an M×N measurement matrix Φ where M<<N, yet the measurement y=Φx preserves the essential information about the K-sparse signal x. An example of the measurement matrix Φ is a random matrix with i.i.d. Gaussian entries. Using any matrix Φ that is incoherent with the matrix Ψ of basis vectors, it is possible to recover the K-sparse signal x from the CS measurements y. The canonical formulation of a CS recovery problem is to solve the l1 minimization problem:
                                          θ            ^                    =                                                    arg                ⁢                                                                  ⁢                min                            θ                        ⁢                                                          θ                                            1                                      ⁢                                  ⁢                              s            .            t            .                                                  ⁢            y                    =                                    Φ              ⁢                                                          ⁢              x                        =            ΦΨθ                                              (        5        )            
This problem requires M=cK measurements where c is some constant. Iterative greedy pursuit algorithms, such as described in J. Tropp and A. Gilbert, “Signal recovery from random measurements via orthogonal matching pursuit”, IEEE Transactions on Information Theory, pp 4655-4666, December 2007, are commonly used for CS recovery, e.g., the orthogonal matching pursuit (OMP) algorithm.
The signal to be estimated for spectrum sensing is the autocorrelation sequence r in equation (1), or equivalently its frequency domain version, the spectrum rf in equation (3). In order to apply CS to spectrum estimation, a sparse representation of r can be used with a sparse vector z on a basis matrix Ψ such that r=Ψz and z contains a lot of zero or near-zero entries.
Z. Tian and G. B. Giannakis, “Compressed Sensing for Wideband Cognitive Radios”, ICASSP, pp 1357-1360, 2007 describes an edge spectrum z as a sparse representation of r. The edge spectrum can be defined as the derivative of a smoothed version of the original signal spectrum:
                    z        =                                                            ⅆ                                                                                              ⅆ                f                                      ⁢                          (                                                r                  ⁡                                      (                    f                    )                                                  *                                  w                  ⁡                                      (                    f                    )                                                              )                                =                                                    ⅆ                                                                                              ⅆ                f                                      ⁢            FFT            ⁢                          {                                                r                  ⁡                                      (                    t                    )                                                  ⁢                                  w                  ⁡                                      (                    t                    )                                                              }                                                          (        6        )            where * denotes the convolution, w(f) is a smoothing function, and w(t) is the inverse Fourier transform of w(f). The convolution of the signal spectrum r(f) with w(f) performed in frequency domain can be implemented in time domain by a multiplication of the autocorrelation sequence r(t) with w(t) and followed by a Fourier transform. In matrix form, the edge spectrum vector z is:
                    z        =        DFWr                            (        7        )                        where                                                      D        =                  [                                                    1                                            0                                            …                                            0                                                                                      -                  1                                                            1                                            ⋱                                            ⋮                                                                    0                                            ⋱                                            ⋱                                            0                                                                    0                                            …                                                              -                  1                                                            1                                              ]                                                is a matrix approximating the derivative operation, W=diag{w(t)} is a diagonal matrix with w(t) on its diagonal, the matrices D, F, and W are of size N×N, the vectors r and z are of size N×1. The edge spectrum vector z is a sparse vector with only a few non-zero entries corresponding to the edges of frequency bands where spectrum levels have some sharp changes.
FIG. 1 shows a signal spectrum r(f) (top) and the corresponding edge spectrum z(f) (bottom). It is clearly derivable that the edge spectrum is sparse in frequency domain with only a few spikes, where a positive spike indicates an increase of spectrum level and a negative spike indicates a decrease.
Based on equation (7), the autocorrelation sequence vector r can be expressed in terms of z:r=(DFW)−1z=Ψz  (8)which shows that r has a sparse representation z in the basis Ψ=(DFW)≦1.
Wideband spectrum sensing can be achieved by performing narrowband sensing on each narrowband frequency channel one at a time. However, this requires an expensive and unfavorable radio frequency (RF) front end with tunable narrowband bandpass filters and also needs knowledge of channelization, i.e., the center frequency and the bandwidth of each narrow band channel, over the wideband of interest.
Another approach is based on sensing the wideband containing multiple narrowband frequency channels at the same time. This requires high-speed and therefore power hungry analog-to-digital converters (ADC) running at e.g., Gbits/second if the total bandwidth of interest is several hundred MHz.
Z. Tian and G. B. Giannakis, “Compressed Sensing for Wideband Cognitive Radios”, ICASSP, pp 1357-1360, 2007 proposed an idea of applying compressive sensing to perform wideband spectrum sensing. However, the compression is applied on the autocorrelation sequence r(t) and the calculation of r(t) requires the original wideband signal x(t) to be sampled at above the Nyquist rate, and therefore the burden of high-speed ADC is not reduced.
Furthermore, US 20080129560 discloses a method for distributed compressive sensing where use is made of a full CS matrix, or a submatrix thereof, and the main focus is on algorithmic efficiency in the recovery algorithm based on joint sparsity amongst measurements at the multiple sensor nodes.